1. Field of the Invention
The present invention relates to a Huffman code decoding circuit for decoding a Huffman code, and more particularly, to a Huffman code decoding circuit capable of executing high-speed Huffman code decoding processing.
2. Description of the Related Art
In conventional decoding of Huffman codes, decoded words are obtained word by word. When in obtaining two decoded words at a time, two decoding tables are prepared and searched to find two decoded words each from an input Huffman code. Then, by adding code lengths of the two decoded words, a leading bit of a next Huffman code to be obtained is determined out of a Huffman code data sequence.
The principle of Huffman codes will be described in brief.
(1) Form a leaf corresponding to each letter.
(2) Form a new nodal point for two leaves whose occurrence probability is the lowest and link the nodal point to the two leaves by two branches.
(3) Label one of the two branches as "0" and the other as "1" and provide the new nodal point with a sum of the probabilities of the two leaves.
(4) With the new nodal point as a new leaf (removing the branches and the leaves reaching out from the nodal point and assuming the nodal point as a leaf), repeat the above operations (2) and (3) until only one leaf is left. Take the last leaf as a root.
Then, a series of "1" and "0" obtained as a result of the tracing of the branches from the root to the leaf corresponding to the letter will represent a code word of the letter (see FIG. 15). In FIG. 15, for example, a code word of the letter "a" whose occurrence probability is 1/12 and a code word of the letter "d" whose occurrence probability is 1/6 are "1111" (code length is 4) and "100" (code length is 3), respectively. Processing for decoding coded data into an original letter is referred to as decoding.
FIG. 13 is a block diagram showing an example of a conventional arrangement of a Huffman code decoding circuit for decoding Huffman codes by obtaining decoded words one by one (referred to as first conventional art). Herein, the maximum code length of a Huffman code is assumed to be 16 bits. In the figure, the Huffman code data sequence "15-0" represents 16 bits of a Huffman code data sequence, and the bit number "15", which is the most significant bit (MSB), is taken as a leading bit.
As shown in FIG. 13, the Huffman code decoding circuit comprises a top, determination unit 500 for obtaining a leading bit of a Huffman code out of a Huffman code data sequence and a decoding table 501 where decoded words and codelengths are stored beforehand. The decoding table 501 includes a ROM (Read Only Memory) etc.
The decoding table 501, as shown in FIG. 16, stores a decoded word of 8 bits and a code length of 5 bits corresponding to a Huffman code applied as an address. For example, a Huffman code for a decoded word "A" is set to be "0101" and that for a decoded word "B" is set to be "0110101". When a Huffman code data sequence "0101x . . . " is input as an address, the decoded word "A" and the code length "4" are output from the decoding table 501, and when a Huffman code data sequence "0110101x . . . " is input as an address, the decoded word "B" and the code length "7" are output from the decoding table 501.
In the decoding table 501 decoded words and code lengths are set corresponding to inputs of the other Huffman codes (address input) in the same manner. The symbol "x" shown in an input bit sequence in FIG. 16 is indicative of a logical value of either "0" or "1" (do not care). Accordingly, when a Huffman code corresponding to the decoded word "A" is "0101", the decoded word "A" and the code length "4" are set for all of 16-bit addresses "01010 . . . 0" to "01011 . . . 1". An initial value of the top determination unit 500 is set to be a leading bit of the 16 bits of an applied Huffman code data sequence.
In FIG. 13, assuming that a Huffman code data sequence "01010110101001 . . . " arrives, the top determination unit 500 receives 16 bits from the top, that is, "01010110101001 . . . "
The top determination unit 500, in which the initial value of a leading bit position corresponds to a leading bit of 16 bits of an applied Huffman code data sequence, sends 16 bits from the top, i.e. "01010110101001 . . . ", to the decoding table 501.
The decoding table 501, which is set to output the decoded word "A" and the code length "4" in response to an input of "0101x . . . ", outputs the decoded word "A" and the code length "4". Then, the obtained coded length "4" is sent to the top determination unit 500.
Based on the applied code length "4", the top determination unit 500 finds that a leading bit of the next Huffman code data sequence corresponds to the 5th bit of the 16-bit data "01010110101001 . . . " Then, 16 bits from the leading bit which is newly obtained by the top determination unit 500, that is, "0110101001 . . . ", are input to the decoding table 501.
The decoding table 501, which is set to output the decoded word "B" and the code length "7" in response to an input of "0110101x . . . ", outputs the decoded word "B" and the code length "7" for the applied "0110101001 . . . " The code length "7" is sent to the top determination unit 500.
Based on the applied code length "7", the top determination unit 500 finds that a leading bit of the next Huffman code data sequence corresponds to the 8th bit of the 16-bit data "0110101001 . . . " Then, 16 bits from the leading bit which is newly obtained by the top determination unit 500, that is, "001 . . . 1", are input to the decoding table 501. Operation will be further repeated in the same manner to execute decoding of coded data.
As a variation of the first conventional art for obtaining decoded words one by one, Japanese Patent Laying Open No. 62-66720, for example, recites a variable-length decoding circuit which requires reduced time for decoding variable-length codes. In order to realize high-speed decoding of variable-length codes within a predetermined time (step ?) irrespective of a code length, the variable-length decoding circuit is structured to decode coded data in each step while reading a code length at the same time and sequentially and controllably input coded data corresponding to an obtained bit position to a decoding table.
More specifically, the variable-length decoding circuit disclosed in Japanese Patent Laying Open No. 62-66720 (referred to as second conventional art) comprises a data register, a code register, address selectors, a leading bit number register, a control circuit and a ROM as a decoding table. 8-bit parallel data output from the code register are applied to corresponding 8 address selectors. Each address selector receives data whose bit order is shifted bit by bit and also receives a bit order selection signal sent from the leading bit number register as a select signal of the address selector. Each address selector outputs a bit in a designated order as 1-bit data to the decoding table (ROM), which table further outputs a decoded word and a code length.
FIG. 14 is a block diagram showing an arrangement example of a conventional Huffman code decoding circuit for decoding Huffman codes by obtaining two decoded words at a time (third conventional art). In FIG. 14, the maximum code length of a Huffman code is set to be 16 bits. In the figure, the Huffman code data sequence "31-0" represents 32 bits of a Huffman code data sequence and the 31st bit, that is, the most significant bit, is taken as a leading bit.
The Huffman code decoding circuit shown in FIG. 14 comprises top determination units 600 and 601 for determining the top of a Huffman code out of a Huffman code data sequence, decoding tables 602 and 603 where a decoded word of 8 bits, a code length of 5 bits and a flag of 1 bit are stored, adders 604 and 605 and a pointer 606.
As illustrated in FIG. 17, the decoding tables 602 and 603 store a decoded word of 8 bits, a code length of 5 bits and a flag of 1 bit corresponding to an input of a Huffman code (address).
Set, for example, are a Huffman code "0101" for a decoded word "A", "0110101" for a decoded word "B", "0111001011001" for a decoded word "C" and "1011010000" for a decoded word "D". The decoding tables 602 and 603 accordingly output the decoded word "A", the code length "4" and the flag "0" in response to an input of "0101x " the decoded word "B", the code length "7" and the flag "0" to an input of "0110101x . . . ", the decoded word "C", the code length "13" and the flag "0" to "0111001011001x . . . ", and the decoded word "D", the code length "10" and the flag "0" to "1011010000x . . ."
The decoding tables 602 and 603 are also set to output the code length "0" and the flag "1" in response to an input of a part of a Huffman code corresponding to a decoded word as an address. More specifically, when a part of "1011010000" indicative of the decoded word "D", for example, 8-bit data "10110100", is input as an address, the decoding tables 602 and 603 output the code length "0" and the flag "1".
In the same manner, the decoding tables 602 and 603 store a decoded word, a code length and a flag corresponding to each address input beforehand.
The initial value of the top determination unit 600 is set to be a leading bit of an applied Huffman code data sequence. On receiving an input of the flag "1", the top determination unit 600 outputs 32 bits from the top of a newly obtained Huffman code. The initial value of the pointer 606 is set to be 0.
It is assumed that a Huffman code data sequence "01010110101011100101100110110100000110101 . . . " is sent to the Huffman decoding circuit of FIG. 14.
The top determination unit 600 receives an input of 32 bits from the top, i.e. "01010110101011100101100110110100". The top determination unit 600, whose initial value is set to be a leading bit of an input Huffman code data sequence, outputs 32 bits from the top, "01010110101011100101100110110100". The output 32-bit data is input to the top determination unit 601.
The decoding table 602 receives an input of the higher 16 bits "0101011010101110" of the above-described 32-bit data. The decoding table 602, which is set to output the decoded word "A", the code length "4" and the flag "0" in response to an input of "0101x . . .", outputs the decoded word "A", the code length "4" and the flag "0". The code length "4" is sent to the top determination unit 601 and the adder 604.
Based on the code length "4" sent from the decoding table 602, the top determination unit 601 finds that the top of the next Huffman code data sequence corresponds to the 5th bit of the 32-bit data "01010110101011100101100110110100", and applies 16 bits starting at the 5th bit position from the top, that is, "0110101011100101", to the decoding table 603.
The decoding table 603, which is set to output the decoded word "B", the code length "7" and the flag "0" in response to an input of "0110101x . . . ", outputs the decoded word "B", the code length "7" and the flag "0". The code length "7" is sent to the adder 604.
In the adder 604, the code length "7", which is the output of the decoding table 603, is added to the code length "4" of the decoded word "A" output from the decoding table 602. The output (4+7=11) of the adder 604 is sent to the adder 605. In the adder 605, the output of the adder 604 and that of the pointer 606 are added. In this case, since the output of the pointer 606 is the initial value "0", 11 (11+0=11) is sent from the adder 605 to the pointer 606.
The output (=11) from the pointer 606 is applied to the top determination unit 600. The top determination unit 600 finds that a leading bit of the next Huffman code corresponds to the 12th bit of the 32-bit data "01010110101011100101100110110100", and applies 16 bits starting at the 12th bit position from the top, i.e. "0111001011001101", to the decoding table 602.
On the other hand, the top determination unit 601 receives an input of 12th to 32th bits from the top, that is, 21-bit data "011100101100110110100".
The decoding table 602, which is set to output the decoded word "C", the code length "13" and the flag "0" in response to an input of "0111001011001x . . . ", outputs the decoded word "C",the code length "13" and the flag "0". The code length "13" is sent to the top determination unit 601 and the adder 604.
Based on the code length "13", which is the output of the decoding table 602, the top determination unit 601 finds that the position of a leading bit of the next Huffman code data sequence corresponds to the 14th bit from the top of the 21-bit data "011100101100110110100", and applies the 8 bits from the 14th to the 21th bit position from the top, i.e. "10110100", to the decoding table 603.
The decoding table 603, which is set as described above to output the code length "0" and the flag "1" in response to an input of 8-bit data "10110100" (a part of "1011010000" indicative of the decoded word "D"), sends the code length "0" to the adder 604 and the flag "1" to the top determination unit 600.
The adder 604 adds the code length "13" of the decoded word "C" and the code length "0" and sends the sum of 13 (=13+0) to the adder 605. The adder 605 adds the output (=11) of the pointer 606 and the output (=13) of the adder 605 and sends the sum of 24 (=11+13) to the pointer 606.
The output (=24) from the pointer 606 is applied to the top determination unit 600. The top determination unit 600 finds that a leading bit of the next Huffman code corresponds to the 25th bit of the 32-bit data "01010110101011100101100110110100".
On the other hand, on receiving the flag "1" and determining that a code length of the Huffman code to be obtained is larger than 8 bits, the top determination unit 600 outputs, as new 32-bit data, 8-bit data "10110100", which are 25th to 32th bits of the 32-bit data "01010110101011100101100110110100", in combination with 24 bits of the next Huffman code data sequence.
With the flag "1", the decoding table 603, for example, may ignore the output of 8-bit decoded word data, using the flag as an enable signal. The above-described processing will be repeated hereinafter to sequentially decode a Huffman code data sequence.
In the first and second conventional art, in which decoded words are obtained one by one, however, the above-described Huffman code decoding circuits require longer processing time to prevent reduction of decoding processing.
On the other hand, the third conventional art, in which the Huffman code decoding circuit is structured to obtain two decoded words at a time, requires a longer pass (signal path) because code length data and the like are to be transmitted from the top determination unit 600 through the decoding table 602, the top determination unit 601, the decoding table 603, the adder 604, the adder 605 and the pointer 606 back to the top determination unit 600 for processing. Therefore, while decoding processing can be executed at a speed higher than that in obtaining a decoded word one by one, a processing speed will be sacrificed by a longer pass (signal path). In other words, it is difficult to improve a processing speed by increasing an operating frequency because a longer pass (signal path) is required.